#include <iostream>
using namespace std;
#include <vector>
#include <list>

//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
//    {
//        if (list1 == nullptr && list2 == nullptr)
//            return nullptr;
//        else if (list1 == nullptr)
//            return list2;
//        else if (list2 == nullptr)
//            return list1;
//
//        if (list1->val < list2->val)
//        {
//            list1->next = mergeTwoLists(list1->next, list2);
//            return list1;
//        }
//        else
//        {
//            list2->next = mergeTwoLists(list1, list2->next);
//            return list2;
//        }
//    }
//};
//
//class Solution {
//public:
//
//    void _hanota(vector<int>& A, vector<int>& B, vector<int>& C, int n)
//    {
//        if (n == 1)
//        {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//
//        _hanota(A, C, B, n - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        _hanota(B, A, C, n - 1);
//
//    }
//
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        int n = A.size();
//        _hanota(A, B, C, n);
//    }
//};


struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

class Solution {
public:

    ListNode* _mergeKLists(vector<ListNode*>& lists, int begin, int end)
    {
        if (begin > end) return nullptr;

        if (begin == end)
            return lists[begin] == nullptr ? nullptr : lists[begin];

        int mid = begin + (end - begin) / 2;
        ListNode* l1 = _mergeKLists(lists, begin, mid);
        ListNode* l2 = _mergeKLists(lists, mid + 1, end);

        ListNode* preHead = new ListNode(-1);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            }
            else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return _mergeKLists(lists, 0, lists.size() - 1);
    }
};

int main()
{
    vector<list<int>> lists(3);
    lists[0].push_back(1);
    lists[0].push_back(4);
    lists[0].push_back(5);

    lists[1].push_back(1);
    lists[1].push_back(3);
    lists[1].push_back(6);

    lists[2].push_back(2);
    lists[2].push_back(6);


    Solution().mergeKLists(lists);
	return 0;
}